//https://leetcode.cn/problems/minimum-moves-to-pick-k-ones/description/?envType=daily-question&envId=2024-07-04


class Solution {
public:
    long long minimumMoves(vector<int>& nums, int k, int maxChanges) {
        vector<int> idx;
        int len{0},max_len{0};
        for(int i{0};i<nums.size();++i)
            if(nums[i])
                max_len=max(max_len,++len),idx.push_back(i);
            else len=0;
        if(max_len>3) max_len=3;
        if(max_len+maxChanges>=k) return k>max_len?(k-max_len)*2+(max_len==0?0:max_len-1):k-1;
        k-=maxChanges;
        int h1{k/2},h2{(k-1)/2};
        vector<long long> pre_sum(idx.size()+1,0LL);
        for(int i{0};i<idx.size();++i) pre_sum[i+1]=pre_sum[i]+idx[i];
        long long min_moves{numeric_limits<long long>::max()};
        for(int right{k-1};right<idx.size();++right){
            int left{right+1-k},mid{right-h2};
            long long moves{(long long)idx[mid]*h1-(pre_sum[mid]-pre_sum[left])+pre_sum[right+1]-pre_sum[mid+1]-(long long)idx[mid]*h2};
            min_moves=min(min_moves,moves);
        }
        return (min_moves+maxChanges*2);
    }
};